package com.hfi.wangzhengalgorithm;

import java.util.Arrays;

/**
 * best case time complexity: O(1) 大部分情况下
 * worst case time complexity: O(n) 个别情况下
 * average time complexity: O(1)
 *
 * 对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，
 * 一般都是一个O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。
 * @author ChangLiang
 * @date 2019/12/10
 */
public class AmortizedTimeComplexity {

    private int[] array;

    public AmortizedTimeComplexity(int n) {
        this.array = new int[n];
    }

    @Override
    public String toString() {
        return "AmortizedTimeComplexity{" +
                "array=" + Arrays.toString(array) +
                '}';
    }

    public int[] getArray() {
        return array;
    }

    public void setArray(int[] array) {
        this.array = array;
    }

    int count = 0;

    /**
     * 实现了一个往数组中插入数据的功能
     * @param val
     */
    public void insert(int val) {
        // 数组满了之后 for循环遍历数组求和
        if (count == array.length) {
            int sum = 0;
            for (int i = 0; i < array.length; ++i) {
                sum = sum + array[i];
            }
            // 将求和之后的 sum 值放到数组的第一个位置
            array[0] = sum;
            // 相当于清空数组 对于可反复读写的存储空间，使用者认为它是空的它就是空的 可以看做是标记清除
            // 没有必要硬删除，再开辟空间 在同一地址空间上再写上新的值
            count = 1;
        }
        // 如果数组一开始就有空闲空间，则直接将数据插入数组
        array[count] = val;
        ++count;
    }
}
